package creative.fire.interview.amazon;

/**
 * @author Eric Han 
 * feuyeux@gmail.com 
 * 2011-7-25
 */
public class RiseAndDropArray {
	private final int[] ia = new int[] { 11, 15, 20, 21, 22, 3, 5, 7, 8, 9, 10 };
	private int m;
	private boolean b;

	/**
	 * search the number and return the position in the array
	 * 
	 * @param x the searched number
	 * @return position if there is no number in the array, return -1
	 */
	public int getPosition(int x) {
		int left = 0;
		int right = ia.length - 1;
		m = (right - left) / 2 + left;
		b = false;
		return getPosition(left, right, x);
	}

	private int getPosition(int left, int right, int x) {
		if (left > right)
			return -1;
		int middle = (right - left) / 2 + left;

		if (ia[middle] == x)
			return middle;
		else if (ia[middle] > x) {
			int p = getPosition(left, middle, x);
			if (p == -1 && !b) {
				b = true;
				return getPosition(m, ia.length - 1, x);
			}
			return p;
		} else {
			int p = getPosition(middle + 1, right, x);
			if (p == -1 && !b) {
				b = true;
				return getPosition(0, m, x);
			}
			return p;
		}
	}

	public void testAll() {
		for (int i = 0; i < ia.length; i++) {
			int p = getPosition(ia[i]);
			System.out.println(p);
		}
	}

	public static void main(String[] args) {
		RiseAndDropArray test = new RiseAndDropArray();
		System.out.println(test.getPosition(725));
		test.testAll();
	}
}
